package class3;

import common.ListNode;
import common.ListNodeUtils;

/**
 * https://leetcode.cn/problems/reverse-linked-list-ii/
 * 反转链表ii
 */
public class Code23_ReverseBetween {

    public static void main(String[] args) {
        ListNode head = ListNodeUtils.getLinked(1, 2, 3); // 5 6 7 1 2 3 4
        int left = 1, right = 3;
        ListNode res = reverseBetween(head, left, right);
        ListNodeUtils.print(res);
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        // 处理边界情况：链表为空、链表只有一个节点，或者 left == right 时不需要反转
        if (head == null || head.next == null || left == right) {
            return head;
        }

        // 移动 cur 到 left 的位置，pre 移动到 left-1 位置
        ListNode cur = head, pre = null;
        int n = 0;
        while (++n != left) {
            pre = cur;
            cur = cur.next;
        }
        // sHead 是需要反转的子链表的头节点
        ListNode sHead = cur;
        int n2 = n;

        // 移动 cur 到 right 的位置
        while (n2++ != right) {
            cur = cur.next;
        }

        ListNode sTail = cur; // sTail 是需要反转的子链表的尾节点
        ListNode tailNext = sTail.next;  // 记录反转后的尾节点的下一个节点

        // 调用 reverse 方法反转从 sHead 到 sTail 的部分
        ListNode newList = reverse(sHead, sTail.next);

        // 连接反转后的子链表与原链表的其他部分
        sHead.next = tailNext;
        if (pre == null) {
            return sTail;
        }
        pre.next = newList;// 连接反转后的部分到原链表

        // 返回新的头节点
        return head;
    }

    // 1 2 3  -> 3 2 1
    public static ListNode reverse(ListNode head, ListNode tail) {
        ListNode next, pre = null;
        // 反转从 head 到 tail 之间的节点
        while (head != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

}
